package LeetCode;

public class LC_516_LongestPalindromicSubsequence {

    public static void main(String[] args) {

    }

    class Solution {

        public int longestPalindromeSubseq(String s) {
            if (s == null || s.length() <= 0) return 0;
            int[][] f = new int[s.length()][s.length()];
            for (int i = s.length() - 1; i >= 0; i--) {
                f[i][i] = 1;
                for (int j = i + 1; j < s.length(); j++) {
                    if (s.charAt(i) == s.charAt(j)) f[i][j] = f[i + 1][j - 1] + 2;
                    else f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
            return f[0][s.length() - 1];
        }

    }

    class Solution_2 {
        public int longestPalindromeSubseq(String s) {
            StringBuilder tmp = new StringBuilder(s);
            String t = tmp.reverse().toString();
            int[][] dp = new int[s.length() + 1][s.length() + 1];
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < s.length(); j++) {
                    if (s.charAt(i) == t.charAt(j)) dp[i + 1][j + 1] = dp[i][j] + 1;
                    else dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
            return dp[s.length()][s.length()];
        }

    }

    class Solution_3 {
        public String longestPalindrome(String s) {
            if (s == null || s.length() <= 1) return s;
            int len = s.length();
            int maxLen = 1;
            boolean[][] dp = new boolean[len][len];
            String longest = null;
            for (int l = 0; l < s.length(); l++) {
                for (int i = 0; i < len - l; i++) {
                    int j = i + l;
                    if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                        dp[i][j] = true;
                        if (j - i + 1 > maxLen) {
                            maxLen = j - i + 1;
                            longest = s.substring(i, j + 1);
                        }
                    }
                }
            }
            return longest;
        }

    }

    class Solution_4 {
        public String longestPalindrome(String s) {
            if (s.isEmpty())
                return null;
            if (s.length() == 1)
                return s;
            String longest = s.substring(0, 1);
            for (int i = 0; i < s.length(); i++) {
                String tmp = helper(s, i, i);
                if (tmp.length() > longest.length()) longest = tmp;
                tmp = helper(s, i, i + 1);
                if (tmp.length() > longest.length()) longest = tmp;
            }
            return longest;
        }

        String helper(String s, int begin, int end) {
            while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
                begin--;
                end++;
            }
            return s.substring(begin + 1, end);
        }

    }
}